package leet.explore;

import common.ListNode;
import common.TreeNode;
import common.Util;
import org.junit.Test;

import java.util.*;

/**
 * @author fance
 * @date 18-6-15 下午12:16
 */
public class First {
    public int removeDuplicates(int[] nums) {
        int i = 0;
        for (int n : nums) {
            if (i < 1 || n > nums[i - 1]) {
                nums[i++] = n;
            }
        }
        return i;
    }

    public int maxProfitII(int[] prices) {
        int maxProfit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                maxProfit += prices[i] - prices[i - 1];
            }
        }
        return maxProfit;
    }

    public void rotate(int[] nums, int k) {
        k = k % nums.length;
        if (k == 0 || nums.length == 1) {
            return;
        }
        reverse(nums,nums.length - k,nums.length - 1);
        reverse(nums,0,nums.length - k - 1);
        reverse(nums,0,nums.length - 1);
    }
    private void reverse(int[] nums,int i,int j) {
        while (i < j) {
            swap(nums,i++,j--);
        }
    }
    private  void swap(int[] a, int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }




    public boolean containsDuplicate(int[] nums) {
        if (nums == null || nums.length < 1) {
            return false;
        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                return true;
            }
        }
        return false;
    }


    public int singleNumber(int[] nums) {
        int res = 0;
        for (int n : nums) {
            res ^= n;
        }
        return res;
    }

    // 1.bf 2.sort 双指针 3.hashmap
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> map = new HashMap<>();
        int[] res = new int[2];
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey( nums[i])) {
                res[0] = map.get(nums[i]);
                res[1] = i;
                return res;
            } else {
                map.put(target - nums[i],i);
            }
        }
        return res;
    }

    // n- 1 + n - 2
    public int climbStairs(int n) {
        if (n < 4) {
            return n;
        }
        int pre = 2;
        int prepre = 1;
        int res = 0;
        for (int i = 3; i <= n; i++) {
            res = pre + prepre;
            prepre = pre;
            pre = res;
        }
        return res;
    }
    // 1.bf 2.保存目前为止最小的数
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length < 1) {
            return 0;
        }
        int curMin = prices[0];
        int maxProfit = 0;
        for (int i = 1; i < prices.length; i++) {
            curMin = Math.min(prices[i],curMin);
            maxProfit = Math.max(maxProfit,prices[i] - curMin);
        }
        return maxProfit;
    }

    public String reverseString(String s) {
        if (s == null || s.length() < 1) {
            return s;
        }
        return new StringBuilder(s).reverse().toString();
    }

    public int reverse(int x) {
        String s = String.valueOf(x);
        boolean neg = false;
        if (s.charAt(0) == '-') {
            neg = true;
            s = s.substring(1);
        }

        s = new StringBuilder(s).reverse().toString();
        int res;
        try {
            res = Integer.parseInt(s);
            if (neg) {
                res = -res;
            }
        } catch (Exception e) {
            res = 0;
        }
        return res;
    }

    public int firstUniqChar(String s) {
        if (s == null || s.length() < 1) {
            return -1;
        }
        Map<Character,Integer> cntMap = new LinkedHashMap<>();
        Map<Character,Integer> indexMap = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            cntMap.put(c,cntMap.getOrDefault(c,0) + 1);
            indexMap.put(c,i);
        }
        Character res = null;
        for (Map.Entry<Character,Integer> entry : cntMap.entrySet()) {
            if (entry.getValue() == 1) {
                res = entry.getKey();
                break;
            }
        }

        return res == null ? -1 : indexMap.get(res);
    }

    public void firstUniqCharI(String s) {
        if (s == null || s.length() < 1) {
            return ;
        }
        Map<Character,Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            map.put(s.charAt(i),map.getOrDefault(s.charAt(i),0) + 1);
        }
        for (int i = 0; i < s.length(); i++) {
            if (map.get(s.charAt(i)) == 1) {
                System.out.println(s.charAt(i));
                break;
            }
        }
    }
    // 1.sort 2.s + t .contains t
    public boolean isAnagram(String s, String t) {
        if (s == null && t == null) {
            return true;
        }
        if (s == null || t == null) {
            return false;
        }
        if (s.length() != t.length()) {
            return false;
        }
        int[] cnt = new int[26];
        for (char c : s.toCharArray()) {
            cnt[c - 'a']++;
        }
        for (char c : t.toCharArray()) {
            if (--cnt[c - 'a'] < 0) {
                return false;
            }
        }

        return true;
    }

    public boolean isPalindrome(String s) {
        if (s == null || s.length() < 1) {
            return true;
        }
        StringBuilder stringBuilder = new StringBuilder("");
        s = s.toLowerCase();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c) || Character.isLetter(c)) {
                stringBuilder.append(c);
            }
        }
        return Util.isPalindrome(stringBuilder.toString());
    }

    public String longestCommonPrefixMine(String[] strs) {
        if (strs == null || strs.length < 1) {
            return "";
        }
        String  minLenS = "";
        int minLen = Integer.MAX_VALUE;
        for (String cur : strs) {
            if (cur.length() < minLen) {
                minLen = cur.length();
                minLenS = cur;
            }
        }
        
        String res = "";
        for (int i = 1; i <= minLenS.length(); i++) {
            String tmp = minLenS.substring(0,i);
            if (isStartWith(strs,tmp)) {
                res = tmp;
            }
        }
        return res;
    }
    private boolean isStartWith(String[] strs,String s) {
        for (int i = 0; i < strs.length; i++) {
            if (!strs[i].startsWith(s)) {
                return false;
            }
        }
        return true;
    }

    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length < 1) {
            return "";
        }
        String pre = strs[0];
        int i = 1;
        while (i < strs.length) {
            while (!strs[i].startsWith(pre)) {
                pre = pre.substring(0,pre.length() - 1);
            }
            i++;
        }
        return pre;
    }

    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1;
    }

    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isSymmetricCore(root.left,root.right);
    }
    private boolean isSymmetricCore(TreeNode root1,TreeNode root2) {
        if (root1 == null && root2 == null) {
            return true;
        }
        if (root1 == null || root2 == null) {
            return false;
        }
        if (root1.val != root2.val) {
            return false;
        }
        return isSymmetricCore(root1.left,root2.right) && isSymmetricCore(root1.right,root2.left);
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> tmp = new ArrayList<>();
            int curSize = queue.size();
            for (int i = 0; i < curSize; i++) {
                TreeNode cur = queue.poll();
                tmp.add(cur.val);
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            res.add(tmp);
        }
        return res;
    }


    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length < 1) {
            return 0;
        }
        int maxSum = nums[0];
        int curSum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (curSum < 0) {
                curSum = nums[i];
            } else {
                curSum += nums[i];
            }
            if (curSum > maxSum) {
                maxSum = curSum;
            }
        }
        return maxSum;
    }



    // n & (n - 1)
    public int reverseBits(int n) {
      /*  String pre = Integer.toBinaryString(n);
        int offset = 32 - pre.length();
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < offset; i++) {
            stringBuilder.append("0");
        }
        String after = stringBuilder.append(pre).reverse().toString();
        return Integer.parseInt(after,2);*/

      int res = 0;
        for (int i = 0; i < 32; i++) {
            res += n & 1;
            n >>>= 1;
            if (i < 31) {
                res <<= 1;
            }
        }
        return res;
    }

    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>();
        if (numRows < 1) {
            return res;
        }

        for (int i = 0; i < numRows; i++) {
            List<Integer> cur = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) {
                    cur.add(1);
                } else {
                    cur.add(res.get(i - 1).get(j - 1) + res.get(i - 1).get(j));
                }
            }
            res.add(cur);
        }
        return res;
    }
    public int missingNumber(int[] nums) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        return (0 + nums.length) * (nums.length + 1) / 2 - sum;
    }

    public boolean isValid(String s) {
        if (s == null) {
            return true;
        }
        LinkedList<Character> stack = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            if (stack.isEmpty()) {
                stack.push(s.charAt(i));
                continue;
            }
            if (s.charAt(i) == ')' && stack.peek() == '(' ||
                    s.charAt(i) == ']' && stack.peek() == '[' ||
                    s.charAt(i) == '}' && stack.peek() == '{') {
                stack.pop();
            } else {
                stack.push(s.charAt(i));
            }

        }
        return stack.isEmpty();
    }

    /**
     * bf failure...
     * @param n
     * @return
     */
    public int countPrimes(int n) {
        int cnt = 0;
        for (int i = 2; i < n; i++) {
            if (isPrime(i)) {
                cnt++;
            }
        }
        return cnt;
    }
    private boolean isPrime(int n) {
        for (int i = 2; i < n; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    public int countPrimesII(int n) {
        if (n < 1) {
            return 0;
        }
        boolean[] notPrimes = new boolean[n];
        int cnt = 0;
        for (int i = 2; i < n; i++) {
            if (notPrimes[i] == false) {
                cnt++;
                for (int j = 2; i * j < n; j++) {
                    notPrimes[i * j] = true;
                }
            }
        }
        return cnt;
    }

    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        ArrayList<Integer> arr = inOrderUnRecur(root);
        for (int i = 0; i < arr.size() - 1; i++) {
            if (arr.get(i) >= arr.get(i + 1)) {
                return false;
            }
        }
        return true;
    }
    private ArrayList<Integer> inOrderUnRecur(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        if (root != null) {
            LinkedList<TreeNode> stack = new LinkedList<>();
            while (!stack.isEmpty() || root != null) {
                if (root != null) {
                    stack.push(root);
                    root = root.left;
                } else {
                    TreeNode cur = stack.pop();
                    res.add(cur.val);
                    root = cur.right;
                }
            }
        }
        return res;
    }


    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums.length == 0) {
            return null;
        }
        return sortedArrayToBSTCore(nums,0,nums.length - 1);
    }
    private TreeNode sortedArrayToBSTCore(int[] nums,int low, int high) {
        if (low > high) {
            return  null;
        }
        int mid = low + (high - low) / 2;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = sortedArrayToBSTCore(nums,low,mid - 1);
        node.right = sortedArrayToBSTCore(nums,mid + 1,high);
        return node;
    }

    public int rob(int[] nums) {
        if (nums == null || nums.length < 1) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        if (nums.length == 2) {
            return Math.max(nums[0],nums[1]);
        }

        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[1],dp[0]);
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1],dp[i - 2] + nums[i]);
        }
        return dp[nums.length - 1];
    }

    public void deleteNode(ListNode node) {
        // 末尾节点
        if (node.next == null) {
            return;
        }
        node.val = node.next.val;
        node.next = node.next.next;

    }

    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;

        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode head = new ListNode(-1);
        ListNode tmp = head;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                tmp.next = l1;
                tmp = tmp.next;
                l1 = l1.next;
            } else {
                tmp.next = l2;
                tmp = tmp.next;
                l2 = l2.next;
            }
        }
        while (l1 != null) {
                tmp.next = l1;

        }
        while (l2 != null) {
                tmp.next = l2;
        }
        return head.next;
    }
    // 1.stack 2.reverse
    public boolean isPalindrome(ListNode head) {
        LinkedList<ListNode> stack = new LinkedList<>();
        ListNode cur = head;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        cur = head;
        while (cur != null) {
            if (cur.val != stack.pop().val) {
                return false;
            }
            cur = cur.next;
        }
        return true;
    }
    public boolean isPalindromeII(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        LinkedList<Integer> stack = new LinkedList<>();

        while (fast != null && fast.next != null) {
            stack.push(slow.val);
            slow = slow.next;
            fast = fast.next.next;
        }

        // 奇数个元素 跳过中间元素
        if (fast != null) {
            slow = slow.next;
        }

        while (slow != null) {
            if (stack.pop() != slow.val) {
                return false;
            }
            slow = slow.next;
        }
        return true;
    }

    public boolean hasCycle(ListNode head) {
        if (head == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;

            if (fast == slow) {
                return true;
            }
        }
        return false;
    }

    public ListNode findPortLoop(ListNode head) {
        /*if (!hasCycle(head)) {
            return null;
        }*/
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                break;
            }
        }

        if (fast == null || fast.next == null) {
            return null;
        }

        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null || n < 1) {
            return head;
        }
        ListNode cur = head;
        // 每走一步,k-- 到末尾  k = k - n;
        while (cur != null) {
            n--;
            cur = cur.next;
        }

        if (n == 0) {
            head = head.next;
        }

        // ++k 到0 时停止,  此时停在n - k 位置.即要删除的节点前一个节点
        if (n < 0) {
            cur = head;
            while (++n != 0) {
                cur = cur.next;
            }
            cur.next = cur.next.next;
        }
        return head;
    }

    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int nums1Index = m - 1;
        int nums2Index = n - 1;
        int resIndex = m + n - 1;
        while (nums1Index >= 0 && nums2Index >= 0) {
            if (nums1[nums1Index] > nums2[nums2Index]) {
                nums1[resIndex--] = nums1[nums1Index--];
            } else {
                nums1[resIndex--] = nums2[nums2Index--];
            }
        }
        while (nums2Index >= 0) {
            nums1[resIndex--] = nums2[nums2Index--];
        }
    }

    // 1.bf 2.二分
    public int firstBadVersion(int n) {
       /* for (int i = 1; i <= n; i++) {
            if (isBadVersion(i)) {
                return i;
            }
        }
        return -1;*/

       /*int lo = 1;
       int hi = n;
       while (lo < hi) {
           int mid = lo + (hi - lo) / 2;
           if (isBadVersion(mid)) {
                hi = mid;
           } else {
                lo = mid + 1;
           }
       }
       return lo;*/
       return -1;
    }

    public void moveZeroes(int[] nums) {
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[index++] = nums[i];
            }
        }
        for (int i = index; i < nums.length; i++) {
            nums[i] = 0;
        }
    }

    public int[] plusOne(int[] digits) {
        if (digits == null || digits.length < 1) {
            return null;
        }
        int res = 0;
        int carry = 0;
        for (int i = digits.length - 1; i >= 0; i--) {
            if (i == digits.length - 1) {
                res = digits[i] + carry + 1;
            } else {
                res = digits[i] + carry;
            }

            if (res > 9) {
                carry = 1;
                res -= 10;
            } else {
                carry = 0;
            }

            digits[i] = res;

        }

        if (carry == 1) {
            int[] ret = new int[digits.length + 1];
            ret[0] = 1;
            for (int i = 0,k = 1; i < digits.length; k++, i++) {
                ret[k] = digits[i];
            }
            return ret;
        }

        return digits;
    }

    public int[] intersect(int[] nums1, int[] nums2) {
        List<Integer> list = new ArrayList<>();
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int i = 0;
        int j = 0;
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] < nums2[j]) {
                i++;
            } else if (nums1[i] > nums2[j]) {
                j++;
            } else {
                list.add(nums1[i]);
                i++;
                j++;
            }
        }
        int[] res = new int[list.size()];
        int k = 0;
        for (Integer num : list) {
            res[k++] = num;
        }
        return res;
    }

    public int strStr(String haystack, String needle) {
        /*if (haystack == null || needle == null) return 0;
        return haystack.indexOf(needle);*/
        for (int i = 0; ; i++) {
            for (int j = 0; ; j++) {
                if (j == needle.length()) {
                    return i;
                }
                if (i + j == haystack.length()) {
                    return -1;
                }
                if (needle.charAt(j) != haystack.charAt(i + j)) {
                    break;
                }
            }
        }
    }



    @Test
    public void test() {
        ListNode head = new ListNode(1);
        ListNode head2 = new ListNode(1);
        ListNode head3 = new ListNode(2);
        ListNode head4 = new ListNode(1);

       /* head.next = head2;
        head2.next = head3;
        head3.next = head4;*/
        System.out.println(isPalindrome(head));
        /*System.out.println(countPrimes(10));
        System.out.println(countPrimesII(10));*/
//        System.out.println(reverseBits(1));
        /*System.out.println(isPalindrome("A man, a plan, a canal: Panama"));
        System.out.println(isPalindrome("race a car"));*/
      /*  System.out.println(reverse(123));
        System.out.println(reverse(-123));
        System.out.println(reverse(120));*/
        /*System.out.println(firstUniqChar("leetcode"));
        System.out.println(firstUniqChar("loveleetcode"));*/

       /* System.out.println(isAnagram("a","b"));
        System.out.println(isAnagram("anagram","nagaram"));
        System.out.println(isAnagram("rat","car"));*/
     //   System.out.println(climbStairs(4));
    }
}
